package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:统计封闭岛屿的数目
 * 二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全
 * 由1包围（左、上、右、下）的岛。
 *
 * 请返回 封闭岛屿 的数目。
 * User:Mr.Du
 * Date:2023/8/24
 * Time:11:47
 */
public class ClosedIsland {

    public static void main(String[] args) {
        int[][] grid = {
                {1,1,1,1,1,1,1,0},
                {1,0,0,0,0,1,1,0},
                {1,0,1,0,1,1,1,0},
                {1,0,0,0,0,1,0,1},
                {1,1,1,1,1,1,1,0}
        };
        int[][] grid1 = {
                {1,1,1},
                {1,0,0},
                {1,1,1}
        };
        int res = closedIsland(grid1);
        System.out.println(res);
    }

    public static int closedIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length, res = 0;
        for(int i = 0;i < m;i++){
            dd(grid, i, 0);
            dd(grid, i, n - 1);
        }
        for(int i = 0;i < n;i++){
            dd(grid, 0, i);
            dd(grid, m - 1, i);
        }
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(grid[i][j] == 0){
                    res++;
                    dd(grid, i, j);
                }
            }
        }
        return res;
    }

    public static void dd(int[][] grid, int i, int j){
        int m = grid.length, n = grid[0].length;
        if(i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 1) return;
        grid[i][j] = 1;
        dd(grid, i, j - 1);
        dd(grid, i, j + 1);
        dd(grid, i - 1, j);
        dd(grid, i + 1, j);
    }

    public static void printArray2(int[][] grid){
        int m = grid.length, n = grid[0].length;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }
}
